// Written by Craig'n'Dave
using System;
using System.Collections.Generic;
// Linked list using an array
namespace ConsoleApp1
{
    class Program
    {
        public class LinkedList
        {
            private static int start = -1;
            private static int next_free = 0;
            private static int max = 10;
            private string[,] llist = new string[max, 2];

            public LinkedList()
            {
                // Initialise the free items list
                for (int index = 0; index < max - 1; index++)
                {
                    llist[index, 1] = Convert.ToString(index + 1);
                }
                llist[max - 1, 1] = "-1";
            }

            public bool add(string item)
            {
                int current_node = start;
                int previous_node = 0;
                int new_node;
                // Check memory overflow
                if (next_free != -1)
                {
                    new_node = next_free;
                    llist[new_node, 0] = item;
                    next_free = Convert.ToInt32(llist[next_free, 1]);
                    // List is empty
                    if (start == -1)
                    {
                        llist[new_node, 1] = "-1";
                        start = new_node;
                    }
                    else
                    {
                        // Item becomes the new start item
                        if (String.Compare(item, llist[current_node, 0]) < 0)
                        {
                            start = new_node;
                            llist[new_node, 1] = Convert.ToString(current_node);
                        }
                        else
                        {
                            // Find correct position in the list
                            while ((current_node != -1) && (string.Compare(llist[current_node, 0], item) < 0))
                            {
                                previous_node = current_node;
                                current_node = Convert.ToInt32(llist[current_node, 1]);
                            }
                            llist[new_node, 1] = llist[previous_node, 1];
                            llist[previous_node, 1] = Convert.ToString(new_node);
                        }
                    }
                    return true;
                }
                else
                {
                    return false;
                }
            }
            
            public void delete(string item)
            {
                int current_node = start;
                int previous_node = 0;
                // Check the list is not empty
                if (current_node != -1)
                {
                    // Item is the start node
                    if (item == llist[current_node, 0])
                    {
                        start = Convert.ToInt32(llist[current_node, 1]);

                    }
                    else
                    {
                        // Find the item in the list
                        while ((current_node != -1) && (item != llist[current_node, 0]))
                        {
                            previous_node = current_node;
                            current_node = Convert.ToInt32(llist[current_node, 1]);
                        }
                        llist[previous_node, 1] = llist[current_node, 1];
                    }
                    // Return deleted node to the free list
                    llist[current_node, 1] = Convert.ToString(next_free);
                    next_free = current_node;
                }

            }
            public List<string> output()
            {
                List<string> items = new List<string>();
                int current_node = start;
                if (start != -1)
                {
                    // Visit each node
                    while (current_node != -1)
                    {
                        items.Add(llist[current_node, 0]);
                        current_node = Convert.ToInt32(llist[current_node, 1]);
                    }
                }
                return items;

            }

        }



        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "Florida", "Georgia", "Delaware", "Alabama", "California", "Wyoming" };
            LinkedList linked_list = new LinkedList();
            // Adding items to the linked list
            for (int index = 0; index < items.Length; index++)
            {
                linked_list.add(items[index]);
            }
            // Deleting items from a linked list
            linked_list.delete("Florida");
            // Output the linked list
            List<string> contents = new List<string>();
            contents = linked_list.output();
            Console.WriteLine(String.Join(", ", contents));
        }
    }
}
